package com.sicheng.蓝桥.练习题.dp.数位;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/31 20:09
 */
public class 度的数量 {
    /**
     * 求给定区间[X,Y]中满足下列条件的整数个数:这个数恰好等于K个互不相等的
     * B的整数次幂之和。
     * 例如，设X=15,Y = 20,K =2,B=2，则有且仅有下列三个数满足题意:
     * 17 =2^4+2^0
     * 18=2^4+2^1
     * 20=2^4＋2^2
     *
     * 输入格式
     * 第一行包含两个整数X和Y，接下来两行包含整数K和B。输出格式
     * 只包含—个整数，表示满足条件的数的个数。
     */

    static int N = 35;
    static int K, B;
    //dp[i,j]  一共i位数, 恰好有j个1
    static int[][] dp = new int[N][N];

    static void init() {//求组合数
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }


    static int dp(int n) {
        if (n == 0)
            return 0;//如果n==0，那么就直接放回0
        List<Integer> v = new ArrayList<>();
        while (n > 0) {
            v.add(n % B);
            n /= B;
        }
        int res = 0;
        int last = 0;//表示已经取了多少个1

        for (int i = v.size() - 1; i >= 0; i--) {//从最高位对每一位数讨论
            int x = v.get(i);
            if (x > 0) {
                //加上第i位取0的时候的组合数，也就是对于后面i位取k-last个1的数量
                res += dp[i][K - last];
                //如果x>1，就可以直接用组合数表示出来，不用进行讨论，也就是i位取1的时候，后面i位随便取k-last-1个1
                if (x > 1) {
                    if (K - last - 1 >= 0)
                        res += dp[i][K - last - 1];
                    break;
                }
                //如果x==1，那么i位取1的时候，还要进行讨论，后面i位不能随便取，也就不是组合数
                else {
                    last++;
                    if (last > K)
                        break;
                }
            }
            // 对于最后一位来特殊来考虑
            if (i == 0 && last == K)
                res++;
        }
        return res;
    }

    public static void main(String[] args) {
        init();
        int l, r;
        Scanner scanner = new Scanner(System.in);
        l = scanner.nextInt();
        r = scanner.nextInt();
        K = scanner.nextInt();
        B = scanner.nextInt();
        System.out.println(dp(r) - dp(l - 1));
    }

}
